package chapter02;

import java.util.ArrayList;
import java.util.List;

public class Combine77 {
    /**
     * 回溯法
     * process(pos,rest,path) 还需要rest个数 从pos位置开始找[pos,n]中任一个数加入到path中
     * 递归出口
     * 1).rest==0
     *    res.add(path)
     *    return
     * 2).否则 尝试pos->n任意一个 加入到路径
     *  for i->[pos,n]
     *      path.add([i])
     *      process(i+1,rest-1,path)
     *      path.remove([i])
     */
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        process(n,1,k,new ArrayList<>());
        return res;
    }

    public void process(int n,int pos,int rest,List<Integer> path){
        if(rest==0){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=pos;i<=n;i++){
            path.add(i);
            process(n,i+1,rest-1,path);
            path.remove(path.size()-1);
        }
    }
}
